package midend.IR_Optimizer;

import midend.Dom_Analysis;
import midend.IR_Value.*;
import midend.IR_Instruction.*;

import java.util.*;

import static midend.IR_Optimizer.New_Mem_To_Reg.dom_frontiersmap;

/**
 * 全局公共子表达式消除优化器
 * 基于支配关系分析，识别和消除冗余的表达式计算
 */
public class GCSE_Optimizer  implements IR_Opt{

    private IR_FuncBlock functionBlock;
    private Dom_Analysis domAnalysis;
    private Map<IR_BaseBlock, Set<IR_BaseBlock>> dominators;
    private Map<IR_BaseBlock, IR_BaseBlock> immediateDominators;

    // 表达式映射表：表达式 -> 计算该表达式的指令
    private Map<String, Instruction> expressionMap;
    // 可用表达式集合：每个基本块中可用的表达式
    private Map<IR_BaseBlock, Set<String>> availableExpressions;
    // 表达式值映射：表达式 -> 对应的值
    private Map<String, IR_Value> expressionValueMap;

    // 每个基本块的Load指令映射：地址 -> Load指令
    private Map<IR_BaseBlock, Map<String, Load_Instruction>> blockLoadMap;
    // 每个基本块输入时的可用Load映射
    private Map<IR_BaseBlock, Map<String, Load_Instruction>> inLoadMap;
    // 每个基本块输出时的可用Load映射
    private Map<IR_BaseBlock, Map<String, Load_Instruction>> outLoadMap;


    Map<IR_Value, LinkedList<IR_Value>> loadopt = new HashMap<>();
    Map<IR_Value,IR_Value> optmap = new HashMap<>();
    ArrayList<Load_Instruction> insertList = new ArrayList<>();

    private void OptimizeinBBload(){
        ArrayList<Instruction> deletelist = new ArrayList<>();
        for(IR_BaseBlock irBaseBlock:functionBlock.get_bb_List()){
            loadopt.clear();
            optmap.clear();
            for(Instruction instruction:irBaseBlock.get_Instruction_List()){
                if(instruction instanceof Load_Instruction loadInstruction){
                    if(loadopt.containsKey(loadInstruction.getPointer())){
                        deletelist.add(loadInstruction);
                        optmap.put(loadInstruction.getRet(),loadopt.get(loadInstruction.getPointer()).getFirst());
                    }
                    else {
                        insertList.add(loadInstruction);
                        loadopt.put(loadInstruction.getPointer(),new LinkedList<>());
                        loadopt.get(loadInstruction.getPointer()).add(loadInstruction.getRet());
                    }
                }
                if(instruction instanceof Store_Instruction storeInstruction){
                    if(loadopt.containsKey(storeInstruction.getPointer())){
                        loadopt.remove(storeInstruction.getPointer());
                    }
                }
            }
            dealwithrename(functionBlock);
        }

        for(Instruction instruction:deletelist){
            instruction.remove();
        }
    }

    private void dealwithrename(IR_FuncBlock irFuncBlock) {
        for(IR_BaseBlock irBaseBlock:irFuncBlock.get_bb_List()) {
            for (Instruction instruction : irBaseBlock.get_Instruction_List()) {
                //条件跳转
                if (instruction instanceof Branch_Instruction branchInstruction && branchInstruction.br_type()) {
                    if (optmap.containsKey(branchInstruction.get_op_index(0))) {
                        branchInstruction.set_Op(0, optmap.get(branchInstruction.get_op_index(0)));
                    }
                } else if (instruction instanceof Calc_Instruction calcInstruction) {
                    if (optmap.containsKey(calcInstruction.get_op_index(1))) {
                        calcInstruction.set_Op(1, optmap.get(calcInstruction.get_op_index(1)));
                    }
                    if (optmap.containsKey(calcInstruction.get_op_index(2))) {
                        calcInstruction.set_Op(2, optmap.get(calcInstruction.get_op_index(2)));
                    }
                } else if (instruction instanceof Cond_Instruction condInstruction) {
                    if (optmap.containsKey(condInstruction.get_op_index(1))) {
                        condInstruction.set_Op(1, optmap.get(condInstruction.get_op_index(1)));
                    }
                    if (optmap.containsKey(condInstruction.get_op_index(2))) {
                        condInstruction.set_Op(2, optmap.get(condInstruction.get_op_index(2)));
                    }
                } else if (instruction instanceof Phi_Instruction phiInstruction) {
                    for (Map.Entry<IR_BaseBlock, IR_Value> entry : phiInstruction.get_ComingValues().entrySet()) {
                        if (optmap.containsKey(entry.getValue())) {
                            phiInstruction.set_ComingValue(optmap.get(entry.getValue()), entry.getKey());
                        }
                    }
                } else if (instruction instanceof Ret_Instruction retInstruction) {
                    if (retInstruction.get_op_index(0) != null && optmap.containsKey(retInstruction.get_op_index(0))) {
                        retInstruction.set_Op(0, optmap.get(retInstruction.get_op_index(0)));
                    }
                } else if (instruction instanceof Store_Instruction storeInstruction) {
                    if (optmap.containsKey(storeInstruction.get_op_index(1))) {
                        storeInstruction.set_Op(1, optmap.get(storeInstruction.get_op_index(1)));
                    }
                } else if (instruction instanceof Type_Trans_Instruction typeTransInstruction) {
                    if (optmap.containsKey(typeTransInstruction.origin())) {
                        typeTransInstruction.set_Origin(optmap.get(typeTransInstruction.origin()));
                    }
                } else if (instruction instanceof Zext_Instruction zextInstruction) {
                    if (optmap.containsKey(zextInstruction.get_op_index(1))) {
                        zextInstruction.set_Op(1, optmap.get(zextInstruction.get_op_index(1)));
                    }
                } else if (instruction instanceof Call_Instruction callInstruction) {
                    if (callInstruction.get_params().size() != 0) {
                        for (int i = 0; i < callInstruction.get_params().size(); i++) {
                            IR_Value para = callInstruction.get_params().get(i);
                            if (optmap.containsKey(para)) {
                                callInstruction.setParams(i, optmap.get(para));
                            }
                        }
                    }
                } else if (instruction instanceof Pointer_Instruction pointerInstruction) {
                    if (optmap.containsKey(pointerInstruction.get_base())) {
                        pointerInstruction.set_Op(1, optmap.get(pointerInstruction.get_base()));
                        pointerInstruction.set_Base(optmap.get(pointerInstruction.get_base()));
                    }
                    for (int i = 0; i < pointerInstruction.get_list().size(); i++) {
                        IR_Value para = pointerInstruction.get_list().get(i);
                        if (optmap.containsKey(para)) {
                            pointerInstruction.set_List(i, optmap.get(para));
                        }
                    }
                }
            }
        }
    }
    /**
     * Load指令优化的主要方法
     */
    private void optimizeLoad() {
        blockLoadMap = new HashMap<>();
        inLoadMap = new HashMap<>();
        outLoadMap = new HashMap<>();

        // 初始化所有基本块的Load映射
        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            blockLoadMap.put(bb, new HashMap<>());
            inLoadMap.put(bb, new HashMap<>());
            outLoadMap.put(bb, new HashMap<>());
        }
        // 使用工作列表算法进行数据流分析
        performLoadDataFlowAnalysis();
        // 执行Load指令消除
        eliminateRedundantLoads();
    }

    /**
     * 执行Load指令的数据流分析
     */
    private void performLoadDataFlowAnalysis() {
        Queue<IR_BaseBlock> workList = new LinkedList<>();
        Set<IR_BaseBlock> inWorkList = new HashSet<>();

        // 初始化工作列表
        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            workList.offer(bb);
            inWorkList.add(bb);
        }

        while (!workList.isEmpty()) {
            IR_BaseBlock bb = workList.poll();
            inWorkList.remove(bb);

            // 保存旧的输出状态
            Map<String, Load_Instruction> oldOut = new HashMap<>(outLoadMap.get(bb));
            // 计算输入状态：合并所有前驱的输出状态
            computeInLoadMap(bb);
            // 计算输出状态：基于输入状态和当前块的指令
            computeOutLoadMap(bb);
            // 如果输出状态发生变化，将后继基本块加入工作列表
            if (!oldOut.equals(outLoadMap.get(bb))) {
                for (IR_BaseBlock successor : getSuccessors(bb)) {
                    if (!inWorkList.contains(successor)) {
                        workList.offer(successor);
                        inWorkList.add(successor);
                    }
                }
            }
        }
    }

    /**
     * 计算基本块的输入Load映射
     */
    private void computeInLoadMap(IR_BaseBlock bb) {
        Map<String, Load_Instruction> inMap = new HashMap<>();
        List<IR_BaseBlock> predecessors = getPredecessors(bb);

        if (predecessors.isEmpty()) {
            // 入口基本块，输入为空
            inLoadMap.put(bb, inMap);
            return;
        }

        // 对于有多个前驱的基本块，只保留在所有前驱中都可用的Load
        boolean first = true;
        for (IR_BaseBlock pred : predecessors) {
            Map<String, Load_Instruction> predOut = outLoadMap.get(pred);

            if (first) {
                // 第一个前驱，直接复制
                inMap.putAll(predOut);
                first = false;
            } else {
                // 后续前驱，取交集
                inMap.entrySet().removeIf(entry -> {
                    String addr = entry.getKey();
                    Load_Instruction load = entry.getValue();

                    // 检查这个前驱是否也有相同地址的Load，并且值相同
                    Load_Instruction predLoad = predOut.get(addr);
                    if (predLoad == null) {
                        return true; // 移除
                    }

                    // 如果Load指令不同，但地址相同，需要检查是否被支配
                    if (predLoad != load) {
                        // 检查其中一个是否支配另一个
                        IR_BaseBlock loadBB = load.get_bb();
                        IR_BaseBlock predLoadBB = predLoad.get_bb();

                        if (loadBB != null && predLoadBB != null) {
                            if (dominators.get(bb).contains(loadBB) &&
                                    dominators.get(bb).contains(predLoadBB)) {
                                // 两个Load都支配当前块，选择支配更强的那个
                                if (dominators.get(predLoadBB).contains(loadBB)) {
                                    entry.setValue(predLoad);
                                    return false;
                                } else if (dominators.get(loadBB).contains(predLoadBB)) {
                                    return false; // 保持当前值
                                }
                            }
                        }
                        return true; // 移除，因为不确定使用哪个
                    }

                    return false; // 保留
                });
            }
        }

        inLoadMap.put(bb, inMap);
    }

    /**
     * 计算基本块的输出Load映射
     */
    private void computeOutLoadMap(IR_BaseBlock bb) {
        Map<String, Load_Instruction> outMap = new HashMap<>(inLoadMap.get(bb));

        // 遍历当前基本块的指令
        for (Instruction instr : bb.get_Instruction_List()) {
            if (instr instanceof Store_Instruction) {
                // Store指令会杀死相关地址的Load
                Store_Instruction storeInstr = (Store_Instruction) instr;
                String storeAddr = getAddressKey(storeInstr.get_op().get(2));

                // 移除可能被这个Store影响的Load
                outMap.entrySet().removeIf(entry -> {
                    String loadAddr = entry.getKey();
                    return mayAlias(loadAddr, storeAddr);
                });

            } else if (instr instanceof Load_Instruction) {
                // Load指令生成新的可用Load
                Load_Instruction loadInstr = (Load_Instruction) instr;
                String loadAddr = getAddressKey(loadInstr.get_op().get(1));

                if (loadAddr != null) {
                    outMap.put(loadAddr, loadInstr);
                }

            } else if (instr instanceof Call_Instruction) {
                // 函数调用可能修改内存，保守地移除所有Load
                outMap.clear();
            }
        }

        outLoadMap.put(bb, outMap);
    }

    /**
     * 消除冗余的Load指令
     */
    private void eliminateRedundantLoads() {
        // 记录需要删除的指令，延迟删除
        Set<Load_Instruction> toDelete = new HashSet<>();

        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            List<Instruction> instructions = new ArrayList<>(bb.get_Instruction_List());
            Map<String, Load_Instruction> currentLoads = new HashMap<>(inLoadMap.get(bb));

            for (int i = 0; i < instructions.size(); i++) {
                Instruction instr = instructions.get(i);

                if (instr instanceof Load_Instruction) {
                    Load_Instruction loadInstr = (Load_Instruction) instr;
                    String loadAddr = getAddressKey(loadInstr.get_op().get(1));

                    if (loadAddr != null && currentLoads.containsKey(loadAddr)) {
                        Load_Instruction existingLoad = currentLoads.get(loadAddr);

                        // 关键修复：确保existing load不会被删除，且真正支配当前load
                        if (!toDelete.contains(existingLoad) &&
                                isLoadDominating(existingLoad, loadInstr, bb) &&
                                isLoadStillValid(existingLoad, loadInstr)) {

                            // 用已有Load的结果替换当前Load的结果
                            IR_Value oldResult = loadInstr.get_op().get(0);
                            IR_Value newResult = existingLoad.get_op().get(0);

                            // 确保新结果确实存在且有效
                            if (newResult != null && isValueStillValid(newResult)) {
                                functionBlock.replaceUseInFunc(oldResult, newResult);
                                toDelete.add(loadInstr); // 标记为待删除
                            } else {
                                // 如果新结果无效，更新当前可用的Load
                                currentLoads.put(loadAddr, loadInstr);
                            }
                        } else {
                            // 更新当前可用的Load
                            currentLoads.put(loadAddr, loadInstr);
                        }
                    } else {
                        // 添加新的Load到当前可用Load集合
                        if (loadAddr != null) {
                            currentLoads.put(loadAddr, loadInstr);
                        }
                    }

                } else if (instr instanceof Store_Instruction) {
                    // Store指令杀死相关的Load
                    Store_Instruction storeInstr = (Store_Instruction) instr;
                    String storeAddr = getAddressKey(storeInstr.get_op().get(2));

                    // 移除可能被这个Store影响的Load，但不要删除它们的定义
                    currentLoads.entrySet().removeIf(entry -> {
                        String loadAddr = entry.getKey();
                        return mayAlias(loadAddr, storeAddr);
                    });

                } else if (instr instanceof Call_Instruction) {
                    // 函数调用清空所有Load
                    currentLoads.clear();
                }
            }
        }

        // 统一删除标记的指令
        for (Load_Instruction loadToDelete : toDelete) {
            //System.out.println(loadToDelete);
            IR_BaseBlock bb = loadToDelete.get_bb();
            if (bb != null) {
                bb.get_Instruction_List().remove(loadToDelete);
            }
        }
    }

    /**
     * 检查Load指令是否仍然有效（没有被中间的Store杀死）
     */
    private boolean isLoadStillValid(Load_Instruction existingLoad, Load_Instruction currentLoad) {
        IR_BaseBlock existingBB = existingLoad.get_bb();
        IR_BaseBlock currentBB = currentLoad.get_bb();

        if (existingBB == null || currentBB == null) {
            return false;
        }

        String loadAddr = getAddressKey(existingLoad.get_op().get(1));
        if (loadAddr == null) {
            return false;
        }

        // 检查从existingLoad到currentLoad之间是否有Store指令杀死了这个地址
        if (existingBB == currentBB) {
            // 同一个基本块，检查中间是否有冲突的Store
            List<Instruction> instructions = existingBB.get_Instruction_List();
            int existingIndex = instructions.indexOf(existingLoad);
            int currentIndex = instructions.indexOf(currentLoad);

            if (existingIndex < 0 || currentIndex < 0 || existingIndex >= currentIndex) {
                return false;
            }

            // 检查中间的指令
            for (int i = existingIndex + 1; i < currentIndex; i++) {
                Instruction instr = instructions.get(i);
                if (killsLoad(instr, loadAddr)) {
                    return false;
                }
            }
            return true;
        } else {
            // 不同基本块，需要检查路径上的所有Store
            return !hasKillingStoreBetween(existingBB, currentBB, loadAddr);
        }
    }

    /**
     * 检查指令是否杀死指定地址的Load
     */
    private boolean killsLoad(Instruction instr, String loadAddr) {
        if (instr instanceof Store_Instruction) {
            Store_Instruction storeInstr = (Store_Instruction) instr;
            String storeAddr = getAddressKey(storeInstr.get_op().get(2));
            return mayAlias(loadAddr, storeAddr);
        } else if (instr instanceof Call_Instruction) {
            // 保守假设：函数调用可能修改任何内存
            return true;
        }
        return false;
    }

    /**
     * 检查从一个基本块到另一个基本块的路径上是否有杀死指定地址的Store
     */
    private boolean hasKillingStoreBetween(IR_BaseBlock fromBB, IR_BaseBlock toBB, String loadAddr) {
        // 简化实现：如果存在支配关系且中间没有明显的Store，则认为安全
        // 更复杂的实现需要路径敏感的分析

        if (!dominators.get(toBB).contains(fromBB)) {
            return true; // 不支配，保守返回true
        }

        // 检查fromBB中existingLoad之后的指令
        // 这里可以添加更精确的分析逻辑

        return false; // 简化假设：支配路径是安全的
    }

    /**
     * 检查一个值是否仍然有效
     */
    private boolean isValueStillValid(IR_Value value) {
        // 检查这个值是否还存在于某个指令的定义中
        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            for (Instruction instr : bb.get_Instruction_List()) {
                if (instr.get_op().size() > 0 && instr.get_op().get(0) == value) {
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 检查一个Load指令是否支配另一个Load指令
     */
    private boolean isLoadDominating(Load_Instruction domLoad, Load_Instruction targetLoad, IR_BaseBlock targetBB) {
        IR_BaseBlock domBB = domLoad.get_bb();

        if (domBB == null) {
            return false;
        }

        if (domBB == targetBB) {
            // 在同一个基本块中，检查指令顺序
            List<Instruction> instructions = targetBB.get_Instruction_List();
            int domIndex = instructions.indexOf(domLoad);
            int targetIndex = instructions.indexOf(targetLoad);
            return domIndex >= 0 && targetIndex >= 0 && domIndex < targetIndex;
        } else {
            // 在不同基本块中，检查基本块的支配关系
            return dominators.get(targetBB).contains(domBB);
        }
    }

    /**
     * 获取地址的键值表示
     */
    private String getAddressKey(IR_Value address) {
        if (address instanceof IR_Int_Value) {
            return "const_addr_" + ((IR_Int_Value) address).get_Int_Value();
        } else if (address instanceof IR_Float_Value) {
            return "const_addr_" + ((IR_Float_Value) address).get_Float_Value();
        } else {
            return address.get_ValueName();
        }
    }

    /**
     * 检查两个地址是否可能别名
     */
    private boolean mayAlias(String addr1, String addr2) {
        // 简单的别名分析：如果地址字符串相同，则可能别名
        // 在更复杂的实现中，这里需要更精确的别名分析
        return addr1.equals(addr2);
    }



    /**
     * 执行全局公共子表达式消除优化
     */
    public void optimize() {
        // 1. 构建表达式映射表
        buildExpressionMap();

        // 2. 计算每个基本块的可用表达式
        computeAvailableExpressions();

        // 3. 执行公共子表达式消除
        eliminateCommonSubexpressions();

    }

    /**
     * 构建表达式映射表，识别可以优化的表达式
     */
    private void buildExpressionMap() {
        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            for (Instruction instruction : bb.get_Instruction_List()) {
                String expr = getExpressionKey(instruction);
                if (expr != null && isOptimizableExpression(instruction)) {
                    expressionMap.put(expr, instruction);
                    expressionValueMap.put(expr, instruction.get_op().get(0));
                }
            }
        }
    }

    /**
     * 计算每个基本块的可用表达式
     */
    private void computeAvailableExpressions() {
        // 使用工作列表算法计算可用表达式
        Queue<IR_BaseBlock> workList = new LinkedList<>();
        Set<IR_BaseBlock> inWorkList = new HashSet<>();

        // 初始化工作列表
        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            workList.offer(bb);
            inWorkList.add(bb);
        }

        while (!workList.isEmpty()) {
            IR_BaseBlock bb = workList.poll();
            inWorkList.remove(bb);

            Set<String> oldAvailable = new HashSet<>(availableExpressions.get(bb));

            // 计算新的可用表达式集合
            computeBlockAvailableExpressions(bb);

            // 如果可用表达式集合发生变化，将后继基本块加入工作列表
            if (!oldAvailable.equals(availableExpressions.get(bb))) {
                for (IR_BaseBlock successor : getSuccessors(bb)) {
                    if (!inWorkList.contains(successor)) {
                        workList.offer(successor);
                        inWorkList.add(successor);
                    }
                }
            }
        }
    }

    /**
     * 计算单个基本块的可用表达式
     */
    private void computeBlockAvailableExpressions(IR_BaseBlock bb) {
        Set<String> available = new HashSet<>();

        // 从所有支配该基本块的前驱块中继承可用表达式
        for (IR_BaseBlock pred : getPredecessors(bb)) {
            if (dominators.get(bb).contains(pred)) {
                available.addAll(availableExpressions.get(pred));
            }
        }

        // 处理当前基本块中的指令
        for (Instruction instruction : bb.get_Instruction_List()) {
            String expr = getExpressionKey(instruction);

            // 如果指令杀死了某些表达式，将其从可用集合中移除
            removeKilledExpressions(instruction, available);

            // 如果指令生成了新的表达式，将其加入可用集合
            if (expr != null && isOptimizableExpression(instruction)) {
                available.add(expr);
            }
        }

        availableExpressions.put(bb, available);
    }

    /**
     * 执行公共子表达式消除
     */
    private void eliminateCommonSubexpressions() {
        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            List<Instruction> instructions = new ArrayList<>(bb.get_Instruction_List());

            for (int i = 0; i < instructions.size(); i++) {
                Instruction instruction = instructions.get(i);
                String expr = getExpressionKey(instruction);

                if (expr != null && isOptimizableExpression(instruction)) {
                    // 检查是否存在支配该指令的相同表达式
                    IR_Value replacement = findDominatingExpression(bb, expr, instruction);

                    if (replacement != null) {
                        // 用已有的值替换当前指令的结果
                        IR_Value oldResult = instruction.get_op().get(0);
                        functionBlock.replaceUseInFunc(oldResult, replacement);

                        // 从指令列表中移除当前指令
                        bb.get_Instruction_List().remove(instruction);
                        instructions.remove(i);
                        i--;

//                        System.out.println("消除公共子表达式: " + expr +
//                                " 在基本块 " + bb.get_ValueName());
                    }
                }
            }
        }
    }

    /**
     * 查找支配当前指令的相同表达式
     */
    private IR_Value findDominatingExpression(IR_BaseBlock currentBB, String expr, Instruction currentInstr) {
        // 在所有支配当前基本块的基本块中查找相同表达式
        for (IR_BaseBlock domBB : dominators.get(currentBB)) {
            if (domBB == currentBB) {
                // 在当前基本块中查找出现在当前指令之前的相同表达式
                for (Instruction instr : domBB.get_Instruction_List()) {
                    if (instr == currentInstr) break;

                    String instrExpr = getExpressionKey(instr);
                    if (expr.equals(instrExpr) && isOptimizableExpression(instr)) {
                        return instr.get_op().get(0);
                    }
                }
            } else {
                // 在支配基本块中查找相同表达式
                for (Instruction instr : domBB.get_Instruction_List()) {
                    String instrExpr = getExpressionKey(instr);
                    if (expr.equals(instrExpr) && isOptimizableExpression(instr)) {
                        return instr.get_op().get(0);
                    }
                }
            }
        }

        return null;
    }

    /**
     * 生成表达式的唯一键
     */
    private String getExpressionKey(Instruction instruction) {
        if (instruction instanceof Calc_Instruction) {
            Calc_Instruction binInstr = (Calc_Instruction) instruction;
            String op = getBinaryOpString(binInstr);
            String left = getValueKey(binInstr.get_op().get(1));
            String right = getValueKey(binInstr.get_op().get(2));

            // 对于交换律运算，确保操作数顺序一致
            if (isCommutativeOp(op)) {
                if (left.compareTo(right) > 0) {
                    String temp = left;
                    left = right;
                    right = temp;
                }
            }

            return op + "(" + left + "," + right + ")";
        } else if (instruction instanceof Cond_Instruction) {
            Cond_Instruction condInstr = (Cond_Instruction) instruction;
            String op = "cmp" + condInstr.get_cond();
            String left = getValueKey(condInstr.get_op().get(1));
            String right = getValueKey(condInstr.get_op().get(2));

            return op + "(" + left + "," + right + ")";
        }

        return null;
    }

    /**
     * 获取值的唯一键
     */
    private String getValueKey(IR_Value value) {
        if (value instanceof IR_Int_Value) {
            return "const_i32_" + ((IR_Int_Value) value).get_Int_Value();
        } else if (value instanceof IR_Float_Value) {
            return "const_f32_" + ((IR_Float_Value) value).get_Float_Value();
        } else {
            return value.get_ValueName();
        }
    }

    /**
     * 获取二元运算的操作符字符串
     */
    private String getBinaryOpString(Calc_Instruction instruction) {
        // 这里需要根据具体的二元指令类型返回操作符
        return instruction.get_op_Type();
    }

    /**
     * 判断操作符是否满足交换律
     */
    private boolean isCommutativeOp(String op) {
        return op.contains("add") || op.contains("mul") ||
                op.contains("and") || op.contains("or") || op.contains("xor");
    }

    /**
     * 判断指令是否可以进行公共子表达式优化
     */
    private boolean isOptimizableExpression(Instruction instruction) {
        // 只优化没有calc cond
        return instruction instanceof Calc_Instruction ||
                instruction instanceof Cond_Instruction;
    }

    /**
     * 移除被当前指令杀死的表达式
     */
    private void removeKilledExpressions(Instruction instruction, Set<String> available) {
        // 如果是Store指令，可能会杀死涉及相同地址的Load表达式
        if (instruction instanceof Store_Instruction) {
            Store_Instruction storeInstr = (Store_Instruction) instruction;
            IR_Value storeAddr = storeInstr.get_op().get(2);

            // 移除可能被该Store指令影响的Load表达式
            available.removeIf(expr -> expr.startsWith("load(") &&
                    expr.contains(getValueKey(storeAddr)));
        }

        // 如果是Call指令，保守地移除所有Load表达式
        if (instruction instanceof Call_Instruction) {
            available.removeIf(expr -> expr.startsWith("load("));
        }
    }

    /**
     * 获取基本块的前驱
     */
    private List<IR_BaseBlock> getPredecessors(IR_BaseBlock bb) {
        List<IR_BaseBlock> predecessors = new ArrayList<>();
        for (IR_BaseBlock block : functionBlock.get_bb_List()) {
            if (getSuccessors(block).contains(bb)) {
                predecessors.add(block);
            }
        }
        return predecessors;
    }

    /**
     * 获取基本块的后继
     */
    private List<IR_BaseBlock> getSuccessors(IR_BaseBlock bb) {
        List<IR_BaseBlock> successors = new ArrayList<>();
        List<Instruction> instructions = bb.get_Instruction_List();

        if (instructions.isEmpty()) {
            return successors;
        }

        Instruction lastInstr = instructions.get(instructions.size() - 1);

        if (lastInstr instanceof Branch_Instruction) {
            Branch_Instruction branchInstr = (Branch_Instruction) lastInstr;
            successors.add(branchInstr.get_block1());
            if (branchInstr.get_block2() != null) {
                successors.add(branchInstr.get_block2());
            }
        }

        return successors;
    }

    @Override
    public void Optimize(IR_FuncBlock functionBlock) {
        if (functionBlock.get_bb_List().size()>3500){
            return;
        }
        this.functionBlock = functionBlock;
        //this.domAnalysis = new Dom_Analysis(functionBlock);
        this.domAnalysis = dom_frontiersmap.get(functionBlock);
        this.dominators = domAnalysis.getDominators();
        this.immediateDominators = domAnalysis.getImmediaDominators();
        this.expressionMap = new HashMap<>();
        this.availableExpressions = new HashMap<>();
        this.expressionValueMap = new HashMap<>();

        OptimizeinBBload();
        optimizeLoad();
        // 初始化每个基本块的可用表达式集合
        for (IR_BaseBlock bb : functionBlock.get_bb_List()) {
            availableExpressions.put(bb, new HashSet<>());
        }
        optimize();
    }
}